Kotlin String Similarity/ca.solostudios.stringsimilarity/QGram

QGram

class QGram(q: Int = DEFAULT_K) : ShingleBased, StringDistance(source)

Implements the Q-gram distance (Ukkonen, 1992) between strings.

The distance between two strings is defined as the number of occurrences of different q-grams in each string: \(\sum_{i=1}^n \lVert \vec{v1_i} - \vec{v2_i} \rVert\). Q-gram distance is a lower bound on Levenshtein distance, but can be computed in \(O(m + n)\), whereas the Levenshtein distance has a time complexity of \(O(m \times n)\).

This distance measure is pseudo-metric. It is not a metric because two non-identical strings can have identical q-gram profiles, resulting in \(distance(X, Y) = 0\) where \(X \neq Y\). However, it does respect the other 3 axioms.

References

Ukkonen, E. (1992-01). Approximate string matching with q-grams and maximal matches. Theoretical Computer Science, 92(1), 191–211. https://doi.org/10.1016/0304-3975(92)90143-4^[sci-hub]

Author

Thibault Debatty, solonovamax

Parameters

The length of each q-gram.

Throws

IllegalArgumentException

if \(q \leqslant 0\)

Constructors

QGram

constructor(q: Int = DEFAULT_K)

Properties

val k: Int

Functions

distance

open override fun distance(s1: String, s2: String): Double

Computes the Q-gram distance of two strings.

fun distance(profile1: Map<String, Int>, profile2: Map<String, Int>): Double

Computes the Q-gram distance of precomputed profiles.

profile

fun profile(string: String): Map<String, Int>

Compute and return the profile of s, as defined by Ukkonen (Ukkonen 1992). The profile is the number of occurrences of k-shingles, and is used to compute q-gram similarity, Jaccard index, etc. Pay attention: the memory requirement of the profile can be up to \(k \times \text{size of the string}\)